package leetcode.test;

import java.util.Random;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 7:41
 *
 * 按照题目描述，如果k是1,对应就是要找最大元素，那么相应的我们的selectK 的索引,就是nums.length一1
 * 如果k是nums.length ，其实就是求最小元素,那么那么相应的我们的selectK 的索引，就是0。
 * 他们之间的转换关系是nums. length一k。
 *
 */
public class Solution_215 {

    public int findKthLargest(int[] nums, int k) {

        return selectk(nums,nums.length-k);
    }

    public  int selectk(int[] arr,int k){

        int left = 0;
        int right = arr.length-1;

        while (left <= right){
            int p =partitiion(arr,left,right);

            if( k == p) {
                return arr[p];
            }

            else if( k < p){
                right =p -1;
            }else{
                left = p+1;
            }

        }


        return -1;

    }







    private  int partitiion(int[] arr, int left, int right){

        int index = (new Random()).nextInt(right-left+1)+left;
        exchange(arr,left,index);




        int i = left + 1;
        int j = right;
        while (true){

            while (i<=j && arr[i] < arr[left]){
                i++;
            }
            while ( j >= i && arr[j] > arr[left]){
                j--;
            }
//            情况1：退出循环
            if( j <= i ) {
                break;
            }


//            情况2：就交换
            exchange(arr,i,j);
            i++;
            j--;
        }

        exchange(arr,left,j);
        return j;

    }

    private  void exchange(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] =arr[j];
        arr[j] = t;
    }
}
